import java.util.*;

/**
 * Created by Terry
 * Description:
 * User: GAOBO
 * Date: 2021-07-29
 * Time: 8:40
 */
public class TestDemo {


    public static List<String> topKFrequent(String[] words, int k) {
        List<String> ret = new ArrayList<>();
        if(words == null) return ret;
        //1、统计每个单词出现的次数  以map的形式进行存储 计算好了每个单词出现的频率
        HashMap<String,Integer> map = new HashMap<>();
        for (String str : words) {
            if(map.get(str) == null) {
                map.put(str,1);
            }else {
                int count = map.get(str);
                map.put(str,count+1);
            }
        }
        //2、建立一个小堆，堆中的每个元素都是Map的Entry
        PriorityQueue<Map.Entry<String,Integer>> minHeap = new PriorityQueue<>(k, new Comparator<Map.Entry<String, Integer>>() {
            //o1 是你  插入的元素  o1 > o2  直接就放到了数组的最后
            @Override
            public int compare(Map.Entry<String, Integer> o1, Map.Entry<String, Integer> o2) {
                if(o1.getValue().compareTo(o2.getValue()) == 0) {
                    //干脆  建堆的时候 按照字母顺序 大堆建  因为最后你会逆置
                    return o2.getKey().compareTo(o1.getKey());
                }
                return o1.getValue()-o2.getValue();
            }
        });

        //3、遍历map里面的元素 先将前K个 建成小堆   然后从第K+1个开始 和堆顶元素比较
        for (Map.Entry<String,Integer> entry : map.entrySet()) {
            //堆 还没要放满 K 个
            if(minHeap.size() < k) {
                minHeap.offer(entry);
            }else {
                Map.Entry<String,Integer> top = minHeap.peek();
                if(top != null) {
                    //1、频率相同 判断key 字母小的 入堆
                    if (top.getValue().compareTo(entry.getValue()) == 0) {
                        if (top.getKey().compareTo(entry.getKey()) > 0) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    } else {
                        //2、
                        if (top.getValue() < entry.getValue()) {
                            minHeap.poll();
                            minHeap.offer(entry);
                        }
                    }
                }
            }
        }

        for (int i = 0; i < k; i++) {
            Map.Entry<String,Integer> top = minHeap.poll();
            if(top != null) {
                String key = top.getKey();
                ret.add(key);
            }
        }

        Collections.reverse(ret);

        return ret;

    }

    public int firstUniqChar(String s) {
        if(s == null) return -1;
        HashMap<Character,Integer> map = new HashMap<>();
        for(char ch : s.toCharArray()) {
            if(map.get(ch) == null) {
                map.put(ch,1);
            }else{
                int count = map.get(ch);
                map.put(ch,count+1);
            }
        }
        for(int i = 0;i < s.length();i++) {
            if(map.get(s.charAt(i)) == 1) {
                return i;
            }
        }
        return -1;
    }





    public static void main(String[] args) {
        String[] strs = {"i", "love", "leetcode", "i", "love", "coding"};
        List<String> ret = topKFrequent(strs,2);
        System.out.println(ret);
    }
}
